// 最基本的set做法
; (function () {
    return
    /**
   * @param {number[]} nums
   * @return {number}
   */
    var findDuplicate = function (nums) {
        let set = new Set()

        for (const val of nums) {
            if (set.has(val)) {
                return val
            } else {
                set.add(val)
            }
        }
    };
})();

// 二分法思想解决问题
// 长度为 n + 1的数组，只有1-n，的数字，说明这里面一定有重复的数字
// 反推可以得到，有重复的数字的数组，数组值在 start-end 之间，
// 那么其长度一定大于 end - start + 1
// 没有重复值的数组，数值在 start-end 之间，长度一定不大于 end - start  + 1，

; (function () {
    return
    var findDuplicate = function (nums) {
        if (nums.length <= 0) {
            return -1;
        }
        let end = nums.length - 1;
        let start = 1;
        let resultLen = 0;
        let result;
        while (end >= start) {
            resultLen = 0;
            let middle = Math.floor((end - start) / 2 + start);
            console.log(middle);
            for (let i = 0; i < nums.length; i++) {
                if (nums[i] <= middle && nums[i] >= start) {
                    resultLen++;
                }
            }
            if (resultLen > (middle - start + 1)) {
                end = middle;
            } else {
                start = middle + 1;
            }
            if (start == end) {
                return start;
            }
        }
        return -1
    };

})();

// 哈希方法,改变了原数组
; (function () {
    return
    var findDuplicate = function (nums) {
        let num
        for (let i = 0; i < nums.length; i++) {
            // 把当前值设为正数
            num = Math.abs(nums[i])
            // 第一次出现的时候设为负数
            if (nums[num] > 0) {
                nums[num] = -nums[num]
            } else {
                // 第二次出现直接可以结束循环
                return num
            }
        }
    };
    findDuplicate([1, 3, 4, 2, 2])
})();

// 利用数组转化成链表的思想
// 思路参考寻找有环链表环起始点
// 如果有环，快指针一定会和慢指针在环上相遇
// 找到相遇点，这时令一个指针从链表头部起始，
// 速度和慢指针相同，他们的相遇点即为所求
; (function () {
    // return
    /**
     * @param {number[]} nums
     * @return {number}
     */
    var findDuplicate = function (nums) {
        let left = 0
        let right = 0

        while (true) {
            left = nums[left]
            right = nums[nums[right]]

            if (left === right) {

                right = 0
                while (true) {
                    left = nums[left]
                    right = nums[right]

                    if (left === right) {

                        return left
                    }
                }


            }
        }
    };
    // [1, 2, 4, 3, 5, 2]
    // 1==>2
    // 1==>2==>4
    // 1==>2==>4==>5
    // 1==>2==>4==>5==>2==>4
    findDuplicate([1, 2, 4, 3, 5, 2])
    findDuplicate([2, 5, 9, 6, 9, 3, 8, 9, 7, 1])



})();


; (function () {
    return
    var findDuplicate = function (nums) {
        let fast = 0;
        let slow = 0;

        while (1) {
            fast = nums[nums[fast]];
            slow = nums[slow];

            if (slow === fast) {
                fast = 0;
                while (nums[slow] != nums[fast]) {
                    fast = nums[fast];
                    slow = nums[slow];
                }
                console.log(nums[slow]);
                return nums[slow];
            }
        }
    };
    findDuplicate([2, 5, 9, 6, 9, 3, 8, 9, 7, 1])
})();